#include <iostream>
#include <string>
#include <list>
#include <sstream>
#include <cctype>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <ctime>

#define INTEIRO 1
#define COMANDO 2
#define ALFANUM 3

using namespace std;

double analisarInfixa(string);

stack<int> pilhaRetorno;

// comandos

bool printMessages = false;

#define MAXCOM 17
#define MAXFUN 11
#define MAXOPT
string arrcomandos[] = {"DATA", "DEF", "DIM", "END", "FOR", "GOSUB", "GOTO",
					    "IF", "LET", "NEXT", "PRINT", "READ", "REM", "RETURN", "STOP", "SETON", "SETOFF"};
vector<string> comandos(arrcomandos, arrcomandos+14);



// GLOBAL OPTIONS

bool optGraus = false;
bool optTrace = false;
bool optNoCient = false;
extern stringstream touc;

string arrNativeFunctions[] = {"SIN", "COS", "TAN", "ATN", "EXP", "ABS", "LOG", "SQR", "RND", "INT", "PI"};

map<string, string> funcoes;

// Tipos

typedef struct proxCommand {
	string comando;
	int numLinha;
	string complemento;
} TProxCommand;

// Protótipos
void executarPrograma(const vector<string> & prog, string & status);
TProxCommand * getCommand(const vector<string> &, int);
int decodeAndExecute(TProxCommand *, const vector<string> &, int);
string getTokenByType (string, int, int &);
void executarLET(TProxCommand *);
void executarPRINT(TProxCommand *);
void executarSETON(TProxCommand *);
void executarSETOFF(TProxCommand *);
double analisarInfixa (string expressao);
string replaceVars(string &);
string replaceFunctions(string &);
string extractArg(string &, int, int &);
string calcFunction(string &, string &, string &);
void executarDUMPVARS();
bool isSeparator(char);
double toRadians(double);
double toGraus(double);
void trim(string&);
void setMessages(bool);

// Outras

bool comparar (string um, string dois) {
	int resultado = um.compare(dois);
	return (resultado < 0);
}

string lastMessage;
int lastLineNumber;

// Variáveis do programa

map<string,double> variaveis;
map<string,double> varusadas;

// Principal

void executarPrograma(const vector<string> & prog, string & status) {
	int proxLinha = 0; // Indica a próxima linha a ser executada. Este é o índice da linha e não o seu número
	TProxCommand * comando;
	while (true) {
		comando = getCommand(prog, proxLinha);
		if (comando == 0) {
			break;
		}
		lastMessage = "";
		lastLineNumber = 0;
		proxLinha = decodeAndExecute(comando, prog, proxLinha);
		if (lastMessage.size() > 0) {
			stringstream saida;
			saida << endl << lastMessage << endl << "Linha: " << (lastLineNumber + 1);
			status = saida.str();
			saida.str("");
			break;
		}
		delete comando;
		if (proxLinha == -999) {
			// Terminar: o último comando mandou terminar ou acabaram os comandos
			break;
		}
	}
}

// Implementação

int decodeAndExecute(TProxCommand * comando, const vector<string> & prog, int lin) {
	int retorno = 0;
	lastLineNumber = lin;
	if (!optTrace) {
		varusadas.clear();
	}
	else {
		touc << endl << "! trace linha: " << (lin + 1) << ", original: " << comando->numLinha;
	}
	if ((unsigned) lin > (prog.size() - 1)) {
		retorno = -999;
	}
	else {
		string * posic = find (arrcomandos, arrcomandos + MAXCOM, comando->comando);
		if (posic >= (arrcomandos + MAXCOM)) {
			if (comando->comando == "DUMPVARS") {
				retorno = lin+1;
				executarDUMPVARS();
			}
			else {
				lastMessage = "**** ERRO: COMANDO DESCONHECIDO: ";
				lastMessage += comando->comando;
				retorno = lin;
			}
		}
		else {
			if (*posic == "LET") {
				retorno = lin+1;
				executarLET(comando);
			}
			else if (*posic == "PRINT") {
					retorno = lin+1;
					executarPRINT(comando);
			}
			else if (*posic == "SETON") {
					retorno = lin+1;
					executarSETON(comando);
			}
			else if (*posic == "SETOFF") {
					retorno = lin+1;
					executarSETOFF(comando);
			}

			if (optTrace) {
				if (varusadas.size() > 0) {
					map<string,double>::iterator it2;
					touc << endl << "------ TRACE DAS VARIAVEIS AFETADAS ------";
					for (it2 = varusadas.begin(); it2 != varusadas.end(); it2++) {
						if (optNoCient) {
							touc << fixed << showpoint << setprecision(7) << endl << (*it2).first << ": " << (*it2).second;
						}
						else {
							touc << endl << (*it2).first << ": " << (*it2).second;
						}
					}
					touc << endl << "------ FIM DO TRACE ------";
					varusadas.clear();
				}
			}
		}
		}
	return retorno;
}

TProxCommand * getCommand (const vector<string>  & prog, int lin) {

	TProxCommand * tp  = 0;

	if ((unsigned) lin <= (prog.size() - 1)) {

		tp = new TProxCommand;
		tp->comando = "";
		tp->numLinha = -1;
		tp->complemento = "";

		int final = 0;
		string tk = getTokenByType (prog[lin], INTEIRO, final);
		if (tk.size() > 0) {
			istringstream iss;
			iss.str(tk);
			iss >> tp->numLinha;
			iss.str("");
		}

		string cmd = getTokenByType (prog[lin], COMANDO, final);
		tp->comando = cmd;

		tp->complemento = prog[lin].substr(final);

	}

	return tp;
}

string getTokenByType (string linha, int tipo, int & lastEnd) {
	string saida = "";
	int x = 0;
	for (x = lastEnd; (unsigned) x < linha.size(); x++) {
		if (isspace(linha[x])
				|| linha[x] == '='
			    || linha[x] == '+'
			    || linha[x] == '-'
			    || linha[x] == '*'
			    || linha[x] == '/'
			    || linha[x] == '^' ) {
			if (saida.size() > 0) {
				break;
			}
			continue;
		}
		else {
			switch (tipo) {
			case INTEIRO:
				if (isdigit(linha[x]) || linha[x] == '.') {
					saida.append(linha,x,1);
				}
				break;
			case COMANDO:
				if (isalpha(linha[x])) {
					saida.append(linha,x,1);
					if (binary_search (comandos.begin(), comandos.end(), saida, comparar)) {
						// Encontrou um comando
						break;
					}
				}
				break;
			case ALFANUM:
				saida.append(linha,x,1);
			}
		}
	}
	lastEnd = x;
	return saida;
}


// Implementações de comandos

void executarLET(TProxCommand * comando) {
	// Encontrar a variável destino
	// Pegar a expressão
	// Resolver a expressão
	int posic = 0;
	string varname = getTokenByType (comando->complemento,ALFANUM, posic);
	string expressao = "";
	if (varname.size() == 0) {
		lastMessage = "**** ERRO LET: FALTA A VARIAVEL.";
	}
	else {

		int posigual = comando->complemento.find("=");
		expressao = comando->complemento.substr(++posigual);


		map<string,double>::iterator it = variaveis.find(varname);
		string expressaoNova = replaceVars(expressao);



		expressaoNova = replaceFunctions(expressaoNova);


		if (lastMessage.size() > 0) {
			return;
		}
		double resultado = analisarInfixa(expressaoNova);
		if (it != variaveis.end()) {
			// Variável existe
			(*it).second = resultado;
		}
		else {
			// Variável não existe
			variaveis[varname] = resultado;
			if (optTrace) {
				varusadas[varname] = resultado;
			}
		}
	}
}

string replaceVars(string & expressao) {
	string saida = expressao;
	map<string,double>::iterator it;
	stringstream ss;
	for (it = variaveis.begin(); it != variaveis.end(); it++) {
		// tem que pesquisar TODAS as posições onde existe a variável e substituir
		int pos = expressao.find((*it).first);
		ss << fixed << showpoint << setprecision(7) << (*it).second;
		while ((unsigned) pos != string::npos) {

			// Testa para ver se é uma variável ou se é parte de outro string

			int posFim = pos + (*it).first.size();
			int posAnt = pos - 1;
			bool ok = true;

			if (posAnt > 0) {
				if (!isSeparator(expressao[posAnt])) {
					ok = false;
				}
			}
			else {
				if ((unsigned)posFim < (expressao.size() - 1)) {
					if (!isSeparator(expressao[posFim])) {
						ok = false;
					}
				}
			}
			if (ok)  {
				varusadas[(*it).first] = (*it).second;
				saida = expressao.replace(pos,(*it).first.size(), ss.str());
			}
			pos = expressao.find((*it).first, pos+1);
		}
		ss.str("");
	}
	return saida;
}


void executarPRINT(TProxCommand * comando) {
	// Encontrar a variável destino
	// Pegar a expressão
	// Resolver a expressão
	int posic = 0;
	string varname = getTokenByType (comando->complemento,ALFANUM, posic);
	string expressao = "";
	if (varname.size() == 0) {
		lastMessage = "**** ERRO PRINT: FALTA A VARIAVEL.";
	}
	else {
		map<string,double>::iterator it = variaveis.find(varname);
		double valor = (*it).second;
		touc << endl << valor;
	}
}

void executarSETON(TProxCommand * comando) {
	trim(comando->complemento);
	if(comando->complemento == "GRAUS") {
		optGraus = true;
	}
	else if (comando->complemento == "TRACE") {
			optTrace = true;
	}
	else if (comando->complemento == "NOCIENT") {
		optNoCient = true;
	}
	else {
		lastMessage = "**** OPCAO INVALIDA.";
	}
	if (printMessages) {
		touc << endl << "? ligando opcao: " << comando->complemento;
	}
}

void executarSETOFF(TProxCommand * comando) {
	trim(comando->complemento);
	if(comando->complemento == "GRAUS") {
		optGraus = false;
	}
	else if (comando->complemento == "TRACE") {
			optTrace = false;
	}
	else if (comando->complemento == "NOCIENT") {
		optNoCient = false;
	}
	else {
		lastMessage = "**** OPCAO INVALIDA.";
	}
	if (printMessages) {
		touc << endl << "? desligando opcao: " << comando->complemento;
	}

}

string replaceFunctions(string & expressao) {
	/*
	 * Procura cada chamada de função dentro da expressao. Para cada chamada, resolve o argumento.
	 * Ao resolver um argumento, ela deve verificar se existem funções. Logo, esta função é recursiva.
	 */
	lastMessage = "";
	string saida = expressao;
	int tam = 0;
	// Primeiro, procurar as funções pré-definidas
	for (int x = 0; x < MAXFUN; x++) {
		int pos = saida.find(arrNativeFunctions[x],0);
		if ((unsigned) pos != string::npos) {
			string argumento = extractArg(saida, pos, tam);
			if (!lastMessage.size() > 0) {
				string custArg = "";
				if (argumento.size() > 0) {
					// Tem que fazer replaceFunctions no argumento
					 argumento = replaceFunctions(argumento);
					// Agora, tem que calcular a expressao no argumento
					 double calculado = analisarInfixa(argumento);
					 stringstream ss;
					 ss << fixed << showpoint << setprecision(7) << calculado;
					 argumento = ss.str();
					 ss.str("");
				}
     			 string resultado = calcFunction(arrNativeFunctions[x], argumento, custArg);
				 saida.replace(pos,tam,resultado);
			}
		}
	}
	return saida;
}

string extractArg(string & expressao, int pos, int & tamanho) {
	string argumento = "";
	int x = 0;
	int inicio = 0;
	int nivel = 1;
	int fim = 0;
	for (x = pos; (unsigned) x < expressao.size(); x++) {
		if (expressao.at(x) == '(') {
			if ((unsigned) (x + 1) < expressao.size()) {
				inicio = x + 1;
				break;
			}
		}
	}

	for (x = inicio; (unsigned) x < expressao.size(); x++) {
		if (expressao.at(x) == '(') {
			nivel++;
		}
		else {
			if (expressao.at(x) == ')') {
				nivel--;
				if (nivel == 0) {
					fim = x - 1;
					break;
				}
			}
		}
	}

	if (inicio == 0 || fim == 0) {
		lastMessage = "**** FUNCAO INVALIDA: ARGUMENTO INCORRETO ****";
	}
	else {
		argumento = expressao.substr(inicio, (fim - inicio)+1);
		tamanho = (x - pos) + 1;
	}

	return argumento;
}

string calcFunction(string & funcao, string & argumento, string & custFunction) {
	string saida = "";

	double valor = 0;
	double resultado = 0;
	istringstream iss;
	iss.str(argumento);
	iss >> valor;
	iss.str("");

	if (funcao == "SQR") {
		// Raiz quadrada
		resultado = sqrt(valor);
	}
	else if (funcao == "LOG") {
		// Logaritmo natural
		resultado = log(valor);
	}
	else if (funcao == "INT") {
		// Truncar decimais
		resultado = floor(valor);
	}
	else if (funcao == "PI") {
		// valor de PI
		resultado = 3.14159265;
	}
	else if (funcao == "SIN") {
		// Seno
		if (optGraus) {
			resultado = sin(toRadians(valor));
		}
		else {
			resultado = sin(valor);
		}

	}
	else if (funcao == "COS") {
		// CoSeno
		if (optGraus) {
			resultado = cos(toRadians(valor));
		}
		else {
			resultado = cos(valor);
		}
	}
	else if (funcao == "TAN") {
		// Tangente
		if (optGraus) {
			resultado = tan(toRadians(valor));
		}
		else {
			resultado = tan(valor);
		}
	}
	else if (funcao == "ABS") {
		// Valor absoluto
		resultado = abs(valor);
	}
	else if (funcao == "ATN") {
		// Arco-Tangente
		if (optGraus) {
			resultado = toGraus(atan(toRadians(valor)));
		}
		else {
			resultado = atan(valor);
		}
	}
	else if (funcao == "EXP") {
		// e elevado a x
		resultado = exp(valor);
	}
	else if (funcao == "RND") {
		// Número aleatório
		if (valor > 0) {
			srand (int(valor));
		}
		else {
			 srand ( time(NULL) );
		}
		resultado = rand();
		resultado = resultado / RAND_MAX;
	}


	stringstream ss;
	//touc<<fixed<<showpoint<<setprecision(2)<<number<<endl;
	ss << fixed << showpoint << setprecision(7) << resultado;
	saida = ss.str();
	ss.str("");
	return saida;
}

void executarDUMPVARS() {
	touc << endl << endl << "**** DUMP DAS VARIAVEIS ****";
	map<string,double>::iterator it;
	for (it = variaveis.begin(); it != variaveis.end(); it++) {
		if (optNoCient) {
			touc << fixed << showpoint << setprecision(7) << endl << (*it).first << ": " << (*it).second;
		}
		else {
			touc << endl << (*it).first << ": " << (*it).second;
		}
	}
	touc << endl << "**** FIM ****" << endl;
}


bool isSeparator(char letra) {
	if (letra == '-' || letra == '+' || letra == '='
			|| letra == '*' || letra == '/' || letra == '^'
			|| letra == '.' || letra == ',' || letra == ' '
		    || letra == '(' || letra == ')'
		    || letra == ':' || letra == ';') {
		return true;
	}
	return false;
}

double toRadians(double grads) {
	return grads * 0.017453293;
}

double toGraus(double rads) {
	return rads * 57.295779513;
}

void trim(string& str) {
  string::size_type pos = str.find_last_not_of(' ');
  if(pos != string::npos) {
    str.erase(pos + 1);
    pos = str.find_first_not_of(' ');
    if(pos != string::npos) str.erase(0, pos);
  }
  else str.erase(str.begin(), str.end());
}

void setMessages(bool m) {
	printMessages = m;
}
